package sjg.DataStructures.search;


/**
 * 二分查找
 * 前提：数组有序
 * 思想：找到
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1000, 1234};

        int index = binarySearch(arr, 0, arr.length-1 , 1234);
        if (index == -1) {
            System.out.println("没有匹配值");
        } else {
            System.out.println("匹配到的索引：" + index);
        }

    }

    /**
     * 传入首位和末位
     * 根据最左和最右，计算出中间位置，和中间位置比大小，然后决定下一轮的最左和最右索引
     *
     * @param arr     目标数组
     * @param left    最左边
     * @param right   最右边
     * @param findVal 目标对象
     */
    private static int binarySearch(int[] arr, int left, int right, int findVal) {
        // 说明递归整个数组，但是没有找到
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (findVal > midVal) { // 向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) { // 向左递归
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }

    }


}
